/* Problem:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
 */

#include <stdio.h>
#include <math.h>
#include "prime.h"

// Good thing double allows 15 integers. LL at the end is for C to
// understand "long long"
#define NUM 600851475143LL

void split(double a, double *biggest_pf)
{
	// first prime number that divides 'a' without a remainder
	double p_for_a = 2; // do not change

	double quotient; // result of division a / p_for_a

	// Find the first prime number that divides a, and set it to p_for_a
	while( 1 ) {
		if ( fmod(a, p_for_a) == 0 ) {
			if( p_for_a > *biggest_pf )
				*biggest_pf = p_for_a;
			break;
		}
		p_for_a = next_prime(p_for_a);
	}

	quotient = a / p_for_a;
	printf("Divide %f by prime %f = %f\n", a, p_for_a, quotient);
	if( is_prime(quotient) ) {
		if ( quotient >= *biggest_pf ) {
			// cool, found the biggest prime factor on the right hand side of
			// factorization
			*biggest_pf = quotient;
		}
		// As we can't divide any more, finish execution.
		return;
	}

	split(a / p_for_a, biggest_pf);
}

int
main(int argc, char *argv[])
{
	// Current biggest prime factor
	double biggest_pf = 1;

	// This program supposes the given number is > 1
	if( NUM == 1 ) {
		printf("%d\n", 1);
		return 0;
	}

	split(NUM, &biggest_pf);

	printf("Biggest prime factor: %.0f\n", biggest_pf);

	return 0;
}
